#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣76. 最小覆盖子串
// 【难度】困难
// 【提交】https://leetcode.cn/problems/minimum-window-substring/submissions/675854659/
// 【标签】滑动窗口；哈希表；双指针
class Solution {
public:
    unordered_map<char, int> need, window;
    
    // 检查当前窗口是否包含t的所有字符
    bool check() {
        for(const auto &p : need) {
            if (window[p.first] < p.second) 
                return false;
        }
        return true;
    }
    
    string minWindow(string s, string t) {
        // 统计t中每个字符的出现次数
        for (const auto &c : t) 
            ++need[c];
            
        int l = 0, r = -1, len = INT_MAX, ansL = -1, ansR = -1;
        
        // 滑动窗口遍历s
        while (r < int(s.size())) {
            // 右指针右移，更新窗口计数
            if(need.find(s[++r]) != need.end()) 
                ++window[s[r]];
                
            // 当窗口满足条件时，尝试收缩左指针
            while (check() && l <= r) {
                // 更新最小窗口
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    ansL = l;
                }
                // 左指针右移，更新窗口计数
                if(need.find(s[l]) != need.end()) 
                    --window[s[l]];
                ++l;
            }
        }
        return ansL == -1 ? string() : s.substr(ansL, len);
    }
};

/**
 * @brief 学习总结：
 * 本题是经典的滑动窗口问题，要求找到包含t所有字符的最小子串。
 * 
 * 解题思路：
 * 1. 使用两个哈希表分别记录需要的字符计数和当前窗口的字符计数
 * 2. 使用左右指针维护滑动窗口
 * 3. 右指针扩展窗口直到包含t的所有字符
 * 4. 左指针收缩窗口寻找最小满足条件的子串
 * 
 * 算法分析：
 * - 时间复杂度：O(|s| + |t|)，每个字符最多被左右指针各访问一次
 * - 空间复杂度：O(|字符集|)，哈希表的大小
 * 
 * 优点：
 * - 滑动窗口思路清晰，能有效解决问题
 * - 使用哈希表记录字符计数，支持任意字符集
 * - 代码结构清晰，逻辑正确
 * 
 * 缺点和改进建议：
 * 1. 原代码存在潜在越界风险，当r达到s.size()时仍会执行++r
 *    改进：在循环开始前检查r是否越界
 * 
 * 2. 优化后的安全版本：
 * 
 * string minWindow(string s, string t) {
 *     unordered_map<char, int> need, window;
 *     for (char c : t) need[c]++;
 *     
 *     int left = 0, right = 0;
 *     int valid = 0;  // 记录窗口中满足need条件的字符个数
 *     int start = 0, len = INT_MAX;
 *     
 *     while (right < s.size()) {
 *         char c = s[right];
 *         right++;
 *         
 *         if (need.count(c)) {
 *             window[c]++;
 *             if (window[c] == need[c])
 *                 valid++;
 *         }
 *         
 *         while (valid == need.size()) {
 *             if (right - left < len) {
 *                 start = left;
 *                 len = right - left;
 *             }
 *             
 *             char d = s[left];
 *             left++;
 *             
 *             if (need.count(d)) {
 *                 if (window[d] == need[d])
 *                     valid--;
 *                 window[d]--;
 *             }
 *         }
 *     }
 *     return len == INT_MAX ? "" : s.substr(start, len);
 * }
 * 
 * 3. 使用valid计数器避免每次检查整个need表，提高效率
 * 
 * 核心思想：
 * 滑动窗口是处理子串问题的强大工具，通过动态调整窗口边界来寻找最优解。
 * 本题的关键在于如何高效判断窗口是否满足条件，以及如何记录最小窗口。
 * 
 * 应用场景：
 * - 最小覆盖子串
 * - 找到字符串中所有字母异位词
 * - 无重复字符的最长子串
 * - 字符串的排列等
 */